package com.lw.leetcode.hash.b;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * hash
 * 1048. 最长字符串链
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/7 21:36
 */
public class LongestStrChain {

    public static void main(String[] args) {
        LongestStrChain test = new LongestStrChain();

        // 4
        String[] arr = {"a", "b", "ba", "bca", "bda", "bdca"};
        int i = test.longestStrChain(arr);

        System.out.println(i);

    }

    public int longestStrChain(String[] words) {
        Map<Integer, Map<String, Integer>> map = new HashMap<>();
        for (String word : words) {
            map.computeIfAbsent(word.length(), v -> new HashMap<>()).put(word, 1);
        }
        int max = 1;
        for (int i = 2; i <= 16; i++) {
            Map<String, Integer> item = map.get(i);
            if (item == null) {
                continue;
            }
            Map<String, Integer> last = map.get(i - 1);
            if (last == null) {
                continue;
            }
            for (String s : item.keySet()) {
                int count = 1;
                int length = s.length();
                for (int j = 0; j < length; j++) {
                    Integer c = last.get(s.substring(0, j) + s.substring(j + 1, length));
                    if (c != null) {
                        count = Math.max(count, c + 1);
                    }
                }
                max = Math.max(max, count);
                item.put(s, count);
            }
        }
        return max;
    }

}
